# TODO: 备选数字有哪些？
numQueue = [1,2,3,4,5,6,7,8,9]
# 用来回溯的栈
resultStack = []
# TODO: check point的格子有哪些？
checkPoint = [2,5,6,7,8]

ROWS = 3
COLS = 3

SUM = 15

# TODO: 如何初始化棋盘？
def InitBoard():
    return [[0 for i in range(0,ROWS)]for j in range(0,COLS)]


board = InitBoard()
print(board)

# TODO: 如何从索引转化为行列组合？
def GetRowColFromIndex(idx):
    return idx // ROWS , idx % ROWS

# TODO: 如何判断即将要放置的数字是否可以放在这个格子里？
# cur_index: 当前考察的格子的索引
# val: 当前打算放在格子里的数字
def IsFillingValueValid(cur_index, val):
    global chackpoint,board
    if not cur_index in chackPoint:
        return True
    
    elif cur_index == 2:
        if board[0][0] + board[0][1] + val == SUM:
            return True
    elif cur_index == 5:
        if board[1][0] + board[1][1] + val == SUM:
            return True
    elif cur_index == 6:
        if board[0][0] + board[1][0] + val == SUM and board[0][2] + board[1][1] + val == SUM:
            return True
    elif cur_index == 7:
        if board[0][1] + board[1][1] + val == SUM:
            return True
    elif cur_index == 8:
        if board[0][2] + board[1][2] + val == SUM and board[2][0] + board[2][1] + val == SUM and board[0][0] + board[1][1] + val == SUM:
            return True            
    return False
    

# TODO：如何获取比传入数字大并且尽可能接近传入的数字，而且还没有使用过的数字？
# 如果找到合适的数字则返回它，否则就返回-1
def GetBiggerUnusedNum(num):
    for i in range(0,len(numQueue)):
        if numQueue[i] > num:
            return i
    return -1

# TODO: 遇到check point格子的时候，计算这个格子应该放什么数字
# 如果计算得到的数字在备选容器里,则返回它，否则返回-1
def CalcCheckPointNum(curIndex):
    global board,numQueue
    r,c = GetRowColFromIndex(curIndex)
    ret = -1 
    if curIndex == 2:
        cp = SUM - board[0][0] - board[0][1]
        if cp in numQueue:
            ret = cp
    elif curIndex == 5:
        cp = SUM - board[1][0] - board[1][1]
        if cp in numQueue:
            ret = cp
    elif curIndex == 6:
        cp = SUM - board[0][0] - board[1][0]
        if cp in numQueue and cp + board[1][1] + board[0][2] == SUM:
            ret = cp
    elif curIndex == 7:
        cp = SUM - board[0][1] - board[1][1]
        if cp in numQueue:
            ret = cp
    elif curIndex == 8:
        cp = SUM - board[2][1] - board[2][0]
        if cp in numQueue and cp + board[1][1] + board[0][0] == cp + board[1][2] + board[0][2] == SUM:
            ret = cp

    return ret

# TODO: 向指定格子放置一个数字
# 放置一个数字的时候不是简单的修改board上对应行列的值，而有三件事要处理，想想看是那三件事
def PutNum(curIndex, num):
    global board,resultstack,numQueue
    r,c = GetRowColFromIndex(curIndex)
    board[r][c] = num
    resultStack.append((curIndex,num))
    numQueue.remove(num)

def main():
    global board, numQueue
    # 当前要填的格子
    print(board)
    curIndex = 0
    
    needRollBack = False
    
    while len(numQueue) > 0:
        # 如果index in checkPoint，则自动补最后一个数字
        if curIndex in checkPoint:
            if CalcCheckPointNum(curIndex) == -1:
                needRollBack = True
                
        r, c = GetRowColFromIndex(curIndex)
        # 是否需要回溯的标志

        if board[r][c] == 0:
            # TODO：如果考察的格子为空格，应该进行哪些处理？
#            if IsFillingValueValid(curIndex,num) == True:
            num = min(numQueue)
            PutNum(curIndex,num)

            if needRollBack == True:
                # TODO：如果需要回溯的时候，需要做那些处理？ 
                curIndex -= 1
                p = resultStack.pop()
                board[r][c] = 0
                for i in range(0,len(numQueue)):
                    if numQueue[i] > p[1]:
                        numQueue.insert((p[1] - 1),p[1])
                        
            else:
                # TODO：不需要回溯的时候，需要做那些处理？
                curIndex += 1

    # TODO：输出找到的九宫格组合：
    print(board)

main()
#print(board)
